#include <iostream>
#include <deque>

using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
    ListNode* reverse(ListNode* head) {
        ListNode* front = NULL;
        ListNode* back = head;
        while (back->next != NULL) {
            ListNode* next = back->next;
            back->next = front;
            front = back;
            back = next;
        }
        back->next = front;
        return back;
    }
public:
    /*
    void reorderList(ListNode* head) {
        if (head == NULL || head->next == NULL || head->next->next == NULL) {
            return;
        }
        deque<ListNode*> list_queue;
        while (head != NULL) {
            list_queue.push_back(head);
            head = head->next;
        }
        ListNode* new_head = list_queue.front();
        ListNode* last_l2 = list_queue.back();
        list_queue.pop_front();
        list_queue.pop_back();
        new_head->next = last_l2;
        if (list_queue.size() % 2 == 0) {
            while (list_queue.size() > 0) {
                ListNode* l1 = list_queue.front();
                ListNode* l2 = list_queue.back();
                list_queue.pop_front();
                list_queue.pop_back();
                last_l2->next = l1;
                l1->next = l2;
                last_l2 = l2;
            }
            last_l2->next = NULL;
        } else {
            while (list_queue.size() > 1) {
                ListNode* l1 = list_queue.front();
                ListNode* l2 = list_queue.back();
                list_queue.pop_front();
                list_queue.pop_back();
                last_l2->next = l1;
                l1->next = l2;
                last_l2 = l2;
            }
            ListNode* l = list_queue.front();
            list_queue.pop_front();
            last_l2->next = l;
            l->next = NULL;
        }
    }*/
    void reorderList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (fast != NULL && fast->next != NULL) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = reverse(slow->next);
        slow->next = NULL;
        slow = head;
        ListNode* ptr = head;
        ListNode* temp_ptr = head->next;
        ptr->next = fast;
        ptr = ptr->next;
        slow = temp_ptr;
        fast = fast->next;
        while (fast != NULL && slow != NULL) {
            ptr->next = slow;
            ptr = ptr->next;
            temp_ptr = ptr->next;
            ptr->next = fast;
            ptr = ptr->next;
            slow = temp_ptr;
            fast = fast->next;
        }
        if (slow != NULL) {
            ptr->next = slow;
            slow->next = NULL;
        } else {
            ptr->next = NULL;
        }
        return;
    }
};


int main() {
    ListNode l1(3), l2(2), l3(0), l4(-4);
    l1.next = &l2;
    l2.next = &l3;
    l3.next = &l4;
    l4.next = NULL;
    Solution solution;
    solution.reorderList(&l1);
    return 0;
}